题目背景
AC_Automation 作为一个可爱的妹子,她喜欢求和而不喜欢乘积。她现在有一个序列,想让你求一些东西。看在她那么可爱的份上,就帮帮她吧。
题目描述
为了让你解出题目,善良的她定义了两个函数: f(l,r) 和 g(l,r) ,满足:
f(l,r)=i=l∑rAi=Al+Al+1+... +Ar
g(l,r)=l≤i≤j≤r∑f(i,j)
(例如:g(1,3)=f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3))
现在她给了你一个长度为 n 的序列 An ,以及 T 个询问,对于第 i 个询问 li,ri ,请你求出对应的 g(li,ri)
由于她太菜了,看在她那么可爱的份上,就帮帮她吧。
输入格式
第一行两个整数 n 和 T ,分别表示序列长度和询问的个数
第二行 n 个正整数 Ai ,表示 AC_Automation 给你的一个序列。
接下来 T 行,每行一个 li 和 ri ,表示 T 个询问。
输出格式
T 行,表示每个 li 和 ri 所对应的 g(li,ri)
样例输入
3 3
1 2 3
1 2
1 3
2 3
样例输出
6
20
10
提示说明
【数据范围与约定】
| 测试点序号 |
n≤ |
T≤ |
| 1∼5 |
100 |
50 |
| 6∼10 |
500 |
100 |
| 11∼15 |
104 |
103 |
| 16∼20 |
106 |
106 |
对于 100% 的数据,1≤n≤106,1≤T≤106,1≤Ai≤32。
题解
首先,很显然我们可以去算每个数的贡献,算得:
g(l,r)=i=l∑r(i−l+1)⋅(r−i+1)⋅Ai
我们用 2 种方法来解这道题:
第一种,整体法 (by 2x6_81)
在开始这个方法之前,先定义一个东西叫做“在 l∼r 之间的贡献三角形”。如下图所示:
| Al |
Al+1 |
⋯ |
Ar |
| r−l+1 |
r−l |
⋯ |
1 |
|
r−l |
⋯ |
1 |
|
|
⋯ |
1 |
|
|
|
⋯ |
|
|
|
1 |
以 l=5,r=8 为例:
| A5 |
A6 |
A7 |
A8 |
| 4 |
3 |
2 |
1 |
|
3 |
2 |
1 |
|
|
2 |
1 |
|
|
|
1 |
可以发现,将每一列的数乘起来再求和就是答案。例如上表,g(5,8)=(4)⋅A5+(3+3)⋅A6+(2+2+2)⋅A7+(1+1+1+1)⋅A8 。
以 n=7 为例,我们先求出 1∼7 的贡献三角形:
| A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
| 7 |
6 |
5 |
4 |
3 |
2 |
1 |
|
6 |
5 |
4 |
3 |
2 |
1 |
|
|
5 |
4 |
3 |
2 |
1 |
|
|
|
4 |
3 |
2 |
1 |
|
|
|
|
3 |
2 |
1 |
|
|
|
|
|
2 |
1 |
|
|
|
|
|
|
1 |
假设我们要求出 l=3,r=5 时的结果,也就是 3∼5 的贡献三角形,就可以这么求:
第一步,求出 1∼7 的贡献三角形中的前 5 列,如下图所示:
| A1 |
A2 |
A3 |
A4 |
A5 |
| 7 |
6 |
5 |
4 |
3 |
|
6 |
5 |
4 |
3 |
|
|
5 |
4 |
3 |
|
|
|
4 |
3 |
|
|
|
|
3 |
第二步,求出 1∼7 的贡献三角形中的第 3∼5 列,如下图所示:
| A3 |
A4 |
A5 |
| 5 |
4 |
3 |
| 5 |
4 |
3 |
| 5 |
4 |
3 |
|
4 |
3 |
|
|
3 |
可以发现,前两步所用的东西是可以通过预处理 (n+1−i)⋅i⋅Ai 的前缀和得到。
第三步,三角形只保留 3 行 3 列,如下图所示:
| A3 |
A4 |
A5 |
| 5 |
4 |
3 |
|
4 |
3 |
|
|
3 |
这里可以通过减去一个 ∑i=352⋅(8−i)⋅Ai 得到该结果,可以发现,这个东西可以通过预处理 Ai 和 (n−i)⋅Ai 的前缀和得到。
最后一步,将每个数减掉 2 ,如下图所示:
| A3 |
A4 |
A5 |
| 3 |
2 |
1 |
|
2 |
1 |
|
|
1 |
这里可以通过减去一个 ∑i=352⋅(i−2)⋅Ai 得到该结果,可以发现,这个东西可以通过预处理 Ai 和 i⋅Ai 的前缀和得到。
综上,可以发现答案是:
i=l∑r(n+1−i)⋅i⋅Ai−(l−1)⋅i=l∑r(n+1−i)⋅Ai−(n−r)⋅i=l∑r(i−l+1)⋅Ai
通过预处理 (n+1−i)⋅i⋅Ai 、i⋅Ai 、(n−i)⋅Ai 和 Ai 的前缀和即可
将其暴力拆开,得到:
i=l∑r((n+1−i)⋅i−(l−1)⋅(n+1−i)−(n−r)⋅(i−l+1))⋅Ai
=i=l∑r(n⋅i+i−i2−l⋅n−l+l⋅i+n+1−i−n⋅i+n⋅l−n+r⋅i−r⋅l+r)⋅Ai
=i=l∑r(−i2−l+l⋅i+1+r⋅i−r⋅l+r)⋅Ai
=i=l∑r(−i2+l⋅i+r⋅i−r⋅l−l+r+1)⋅Ai
=i=l∑r(−i2+(l+r)⋅i−(r+1)⋅(l−1))⋅Ai
预处理 −i2⋅Ai 、i⋅Ai 和 Ai 的前缀和即可
这个方法非常简单,我们对于每个 Ai 的贡献进行分解,得到如下变换:
i=l∑r(i−l+1)⋅(r−i+1)⋅Ai=i=l∑r(−i2+(l+r)⋅i+(r+1)⋅(−l+1))⋅Ai
预处理 −i2⋅Ai 、i⋅Ai 和 Ai 的前缀和即可